The Fast Fourier Transform (FFT) is widely used for generation of spectrum information from sets of data which vary in time (spectral analysis), and in the reverse direction for determining the time function which is equivalent to a particular spectrum (filtering). The FFT is widely used in communications applications such as in demultiplexing, and is generally described by Brigham in “The Fast Fourier Transform and its Applications”, Prentice-Hall, 1988. In its demultiplexing role, the algorithm is used in multicarrier demultiplexing, as described by Crochiere et al. in “Multirate Digital Signal Processing, Prentice-Hall, 1983. The FFT can be implemented as a decimation-in-time function or as a decimation-in-frequency (DIF) function or algorithm, and can be implemented in hardware, in software running on a general-purpose processor, or as a pipelined structure adapted for the application. The pipelined structure is very advantageous for many applications.
FIG. 1 is an illustration of the transposed canonical signal flow graph 10 which is ordinarily used to explain the operation of the FFT. In FIG. 1, the flow graph includes a plurality 2S of input nodes or points at the left of the FIGURE, where S is an integer representing the number of FFT stages. The value of 2S is sixteen in the particular example of FIG. 1, and these input nodes or points are numbered 0 to 15. There are similarly sixteen output ports at the right, numbered in like fashion. Lying between the input and output ports are S stages of butterflies, where S=4 in this example. The first stage (stage 1) of butterflies has paired inputs and outputs, so that the sixteen input ports are coupled to eight individual butterfly groups. In particular, input nodes 0 and 1 are coupled to a first butterfly, designated 0, of the first butterfly group of stage 1. Similarly, input nodes 2 and 3 are coupled to a second butterfly of the second butterfly group of stage 1, input nodes 4 and 5 are coupled to a third butterfly group of stage 1, input nodes 6 and 7 are coupled to a fourth butterfly group of stage 1, and so forth. Each of the butterfly groups in the first stage includes a single butterfly, designated 0 at the crossing of the two lines of the butterfly. The last butterfly group of stage 1 is the eighth butterfly group, which is connected to input nodes 14 and 15. Each butterfly group of stage 1 of FIG. 1 has a pair of output nodes. In FIG. 1, the output nodes of the first butterfly are designated 0 and 1, the output nodes of the second butterfly are designated 2 and 3, the output nodes of the third butterfly group are designated 4 and 5, the output nodes of the fourth butterfly group are designated 6 and 7, the output nodes of the fifth butterfly group are designated 8 and 9, the output nodes of the sixth butterfly group are designated 10 and 11, and the output nodes of the seventh butterfly group are designated 12 and 13. The output nodes of the eighth butterfly group are designated 14 and 15.
The output sum (+) and difference (−) signals from each butterfly group of the first stage of FIG. 1 appear at first-stage output nodes 0 through 15, corresponding to the second-stage input nodes, which are grouped into sets of four. Thus, first-stage output ports 0, 1, 2, and 3 correspond to input ports 0, 1, 2, and 3 of the first butterfly group of the second stage of butterflies. First stage output ports 4, 5, 6, and 7 correspond to second-stage input ports 0, 1, 2, and 3 of the second group of butterflies of the second stage. First-stage output ports 8, 9, 10, and 11 correspond to input ports 0, 1, 2, and 3, respectively, of the third set of butterflies of the second stage. Lastly, output ports 12, 13, 14, and 15 of the first stage of butterflies correspond to input ports 0, 1, 2 and 3 of the fourth set of butterflies of the second stage. The second stage of butterflies is thus seen to be divided into four groups, each containing two butterflies, designated 0 and 1. The first and third inputs of each butterfly group of the second stage share the first butterfly of the group, namely the one designated 0, and the second and fourth inputs share a second butterfly, namely the one designated 1. This is true for each of the four groups or sets of butterflies of the second stage of FIG. 1.
In the arrangement of FIG. 1, the third-stage butterflies are grouped into two sets, each having its input ports numbered from 0 to 7. Thus, output port 0 of the first butterfly group of stage 2 is connected to or corresponds to input port 0 of the first group or set of butterflies of stage 3, output port 1 of the first butterfly group of stage 2 corresponds to input port 1 of the first butterfly group of stage 3, output port 2 of the first butterfly group of stage 2 corresponds to input port 2 of the first butterfly group of stage 3, and output port 3 of the first butterfly group of stage 2 corresponds to input port 3 of the first group of butterflies of the third stage of butterflies. Output port 0 of the second butterfly group of stage 2 corresponds to input port 4 of the first stage of butterflies of stage 3, output port 1 of the second butterfly group of stage 2 corresponds to input port 5 of the first butterfly group of stage 3 of butterflies, output port 2 of the second group of butterflies of stage 2 corresponds to input port 6 of the first butterfly group of stage 3, and output port 3 of the second group of butterflies of stage 2 corresponds to input port 7 of the first butterfly group of stage 3. In a similar manner, output ports 8, 9, 10, and 11 of the third butterfly group of stage 2 correspond to input ports 0, 1, 2, and 3, respectively, of the second group of butterflies of the third stage of FIG. 1. Lastly, output ports 12, 13, 14, and 15 of the fourth butterfly group of stage 2 of FIG. 1 correspond to input ports 4, 5, 6, and 7, respectively. Thus, the third stage of butterflies is partitioned into two groups, namely the upper group of four butterflies, designated 0, 1, 2, and 3, associated with, or having, output ports 0 through 7, respectively, and the lower group of four butterflies, also designated 0, 1, 2, and 3, having output ports 8 through 15.
In FIG. 1, output ports or nodes 0, 1, 2, 3, 4, 5, 6, and 7 of the first butterfly group of stage 3 correspond to like-numbered input ports of the single butterfly group of stage 4, and output ports 8, 9, 10, 11, 12, 13, 14, and 15 of the second butterfly group of stage 3 correspond to like-numbered input ports of the single butterfly group of stage 4. Thus, the butterfly group of the last or fourth stage of butterflies is in one monolithic group, or in other words is not divided into groups, and its eight individual butterflies are designated 0 through 7. More particularly, butterfly 0 of the fourth-stage butterfly group is associated with output nodes 0 and 8, butterfly 1 is associated with output ports 1 and 9, butterfly 3 is associated with output ports 2 and 10, butterfly 4 is associated with output ports 3 and 11, butterfly 5 is associated with output ports 4 and 12, butterfly 6 is associated with output ports 5 and 13, butterfly 7 is associated with output ports 6 and 14, and butterfly 8 is associated with output ports 7 and 15.
FIG. 2a illustrates a single butterfly representation of a first type, which can apply to any one butterfly or line-crossing of FIG. 1, and FIG. 2b represents a different type of butterfly, which can also be used in the representation of FIG. 1. In FIG. 2a, the butterfly is of the type used with a decimation-in-frequency (DIF) FFT operation when applied to FIG. 1. The butterfly of FIG. 2b is of the type used with a decimation-in-time (DIT) FFT operation when applied to FIG. 1. FIG. 2a illustrates one butterfly representation, which can apply to any one butterfly of line-crossing of FIG. 1. In FIG. 2a, the butterfly is of a type used with a Decimation-in-frequency (DIF) FFT operation when applied to FIG. 1. In the arrangement of FIG. 2a, the butterfly 220 includes an input node coupled to an input port A, another input node coupled to another input port B, a + output node coupled to an output port C, and a further − output node coupled by way of a weighting or twiddle factor multiplier 222 to output port D. The butterfly 220 of FIG. 2a can be represented by the symbol designated 226.
In the arrangement of FIG. 2b, the butterfly 210 includes an input coupled to port A, and a second input node coupled to input port B. In addition, the + output node of the butterfly of FIG. 2b is coupled to an output port C, and the − output nod is coupled to output port D. A weighting or twiddle factor multiplier 214 is coupled between input port B and the lower input node 212 of butterfly 210. The butterfly of FIG. 2b can be represented by the symbol designated 216.
In operation of the flow graph of FIG. 1 for use with a prior-art FFT, the input data points are assumed to have been buffered, and a set of sixteen data points is available for application to the input nodes of the flow graph of FIG. 1. Thus, a particular complex number is applied to each input node 0 through 15.
In general, there are S stages, which number four in the arrangement of FIG. 1. At the  stage (where i≦S and i≧1), there are 2S−i butterfly groups, each group containing 2i−1 butterflies. The input ports of the ith stage butterfly group are labelled from 0 to (2i−1). Input port j (0≦j≦2i−1) and (j+2i−1% 2i) share the same butterfly.
The operation of an FFT can be implemented in software. An illustrative example of a prior-art software for performing an FFT, in C language, is
void FFT(int N, int s, int **indexSet, complex*x){int i, j, j2, k;/ /countersint nRep;/ /Index spacing betweenadjacent butterfly Groupint numBFL;/ /number of Butterfliesper Groupfloat twoPi;float ang;/ /twiddle factor unitphasefloat TWF;/ / twiddlefactorfloat c,s;/ /Cosine and Sinestorage variablecomplex tempData;Nrep=1;twoPi=2*3.14159265;for (i=0;i<s; i++)/ /number ofstages loop{numBFL=Nrep; / /number ofbutterflies per group at stage sNrep=2*nRep;ang=twoPi/nRep;for (j=0;j<numBFL;j++){/ /Calculate thetwiddle factorsTWF=ang*j;c=cos(TWF);s=sin(TWF);/ /update the datafor (k=j: k<N; k+=nRep){j2=k+numBFL;tempData=x(j2) *CMPLX(c,s);x(j2) =x(k) − tempData;x(k) =x(k) + tempData;}}}}The underlined portions of the prior-art FFT processing are those in which changes are made to implement the method of the invention, as described below.
In general, the entire FFT is calculated in the prior art, even if only a few of the output points are required. There are applications in which the required FFT outputs are sparse, as for example in which the desired outputs correspond to only certain bins of the FFT output or in narrow frequency windows. In the multicarrier demodulation context, it might be desired to extract only one or a few noncontiguous carriers from the multicarrier input signal. FFT pruning is known for reducing the computational burden. Such pruning is described by Markel in “FFT pruning”, published at pp 305-311 in the IEEE Transactions on Audio Electroacoustics, Vol. Au-19, December 1971; Skinner in “Pruning the decimation-in-time FFT algorithm,” published at pp 193-194 of IEEE Trans. Acoustics, Speech, and Signal Processing, vol ASSP-24, April 1976; Sreenivas et al., in “FFT algorithms for both input and output pruning,” published at pp 291-292 of IEEE Trans. Acoustics, Speech, and Signal Processing, vol ASSP-27, June 1979; Sreenivas et al., in “High-resolution Narrow-Band Spectra by FFT pruning,” published at pp 254-257 of IEEE Trans. Acoustics, Speech, and Signal Processing, vol ASSP-28, April 1980; and Nagai, in “Pruning the decimation-in-time FFT Algorithm with frequency shift,” at pp 1008-1010 of IEEE Trans. Acoustics, Speech, and Signal Processing, vol ASSP-34, August 1986. However, the pruning described in these sources appears to be applied only when the set of output points or bins is continuous, which is to say when the outputs are in continuous windows, or require special structures. It should be noted that, since the FFT is cyclic, outputs are (or can be considered to be) continuous when they extend from the highest-numbered back to zero. In our example, that is to say, that the output node or port group numbered 14, 15, 0, 1 is a continuous or contiguous group, since the transition between nodes numbered 0 and 15 is not considered to be discontinuous. On the other hand, the output node group 14, 0, 1 would be considered to be discontinuous, since a non-selected port (port 15) lies within the sequence.
Improved pruning techniques for FFT are desired.